home *** CD-ROM | disk | FTP | other *** search
/ Aminet 30 / Aminet 30 (1999)(Schatztruhe)[!][Apr 1999].iso / Aminet / dev / lang / SmallEiffel.lha / SmallEiffel / lib_show / pyramid.e < prev    next >
Text File  |  1998-12-22  |  6KB  |  244 lines
  1. --          This file is part of SmallEiffel The GNU Eiffel Compiler.
  2. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  3. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr 
  4. --                       http://www.loria.fr/SmallEiffel
  5. -- SmallEiffel is  free  software;  you can  redistribute it and/or modify it 
  6. -- under the terms of the GNU General Public License as published by the Free
  7. -- Software  Foundation;  either  version  2, or (at your option)  any  later 
  8. -- version. SmallEiffel is distributed in the hope that it will be useful,but
  9. -- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. -- or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU General Public License 
  11. -- for  more  details.  You  should  have  received a copy of the GNU General 
  12. -- Public  License  along  with  SmallEiffel;  see the file COPYING.  If not,
  13. -- write to the  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14. -- Boston, MA 02111-1307, USA.
  15. --
  16. class PYRAMID 
  17. --
  18. -- Solving the problem of the Pyramid for small pyramid only.
  19. --
  20. --| This program uses the back-tracking method.
  21. --| Its goal is to try to fill a pyramid by making a substraction  
  22. --| between two succesive columns and to take its absolute value.  
  23. --| The result is put on the next line.   
  24. --| Example :
  25. --|  6 14 15 3 13
  26. --|   8 1 12 10
  27. --|    7 11 2
  28. --|     4  9
  29. --|       5 
  30. --
  31. -- See also pyramid2, which run faster than this first solution.
  32.    
  33. inherit 
  34.    ANY 
  35.       redefine 
  36.      out_in_tagged_out_memory
  37.       end;
  38.    
  39. creation make
  40.  
  41. feature 
  42.    
  43.    size : INTEGER;
  44.    
  45.    make is
  46.       do
  47.      if argument_count = 0 then
  48.         std_output.put_string("Want to compute a small pyramid ?%N%
  49.                   %Enter a small number (> 1) : ");
  50.         std_output.flush;
  51.         std_input.read_integer;
  52.         size := std_input.last_integer;
  53.      else
  54.         size := argument(1).to_integer;
  55.      end;
  56.      if size <= 1 then
  57.         std_output.put_string("You feel sick ?%N");
  58.      elseif size > biggest_one then
  59.         std_output.put_string("Value too big for this method.%N");
  60.      else
  61.         !!elem.make(1,max);
  62.         if fill_up(1) then
  63.            std_output.put_string("Full pyramid :%N");
  64.            print_on(std_output);
  65.         else
  66.            std_output.put_string("Unable to fill_up such one.%N");
  67.         end;
  68.      end;
  69.       end; -- make
  70.    
  71.    max : INTEGER is
  72.       do
  73.          Result := (size * (size + 1)) // 2;
  74.       end; -- max
  75.    
  76.    out_in_tagged_out_memory is
  77.       local
  78.      lig,col,nb : INTEGER;
  79.       do
  80.      from  
  81.         lig := 1;
  82.         col := 1;
  83.         nb := 0;
  84.      until
  85.         nb = max
  86.      loop
  87.         if col = 1 then
  88.            tagged_out_memory.extend('%N');
  89.         end;
  90.         (elem.item(indice(lig,col))).append_in(tagged_out_memory);
  91.         tagged_out_memory.append(" ");
  92.         if col = size - lig + 1 then
  93.            col := 1 ;
  94.            lig := lig + 1 ;
  95.         else
  96.            col := col + 1;
  97.             end;
  98.         nb := nb + 1;
  99.      end;
  100.      tagged_out_memory.extend('%N');
  101.       end; 
  102.    
  103.    belongs_to(nb : INTEGER): BOOLEAN is
  104.       require
  105.      nb_trop_petit: nb >= 1;
  106.      nb_trop_grand: nb <= max;
  107.       local
  108.      i : INTEGER;
  109.      trouve : BOOLEAN;
  110.       do
  111.      from  
  112.         i := 1;
  113.         trouve := false;
  114.      until
  115.         ((i > max) or trouve)
  116.      loop
  117.         trouve := (nb = elem.item(i));  
  118.         i := i + 1;
  119.      end;
  120.      Result := trouve;
  121.       end; -- belongs_to
  122.    
  123.    propagate (col, val_column_1: INTEGER): BOOLEAN is
  124.       require
  125.      val_column_1 >= 1;
  126.      val_column_1 <= max;
  127.      col >= 1;
  128.      col <= size;
  129.       local
  130.      stop : BOOLEAN;
  131.      lig : INTEGER;
  132.      val : INTEGER;
  133.       do
  134.          if belongs_to(val_column_1) then
  135.             Result := false ;
  136.          else
  137.             from  
  138.                elem.put(val_column_1,indice(1,col));
  139.                lig := 1;
  140.                val := val_column_1;
  141.                stop := false;
  142.                Result := true;
  143.             until
  144.                stop
  145.             loop
  146.                lig := lig + 1;
  147.                if lig > col then
  148.                   stop := true;
  149.                else
  150.                   val := val - elem.item(indice(lig-1,col-lig+1));
  151.                   if val < 0 then -- valeur absolue !
  152.                      val := - val ;
  153.                   end;
  154.                   if belongs_to(val) then
  155.                      clear_column(col);
  156.                      stop := true;
  157.                      Result := false;
  158.                   else
  159.                      elem.put(val,indice(lig,col-lig+1));
  160.                   end;
  161.                end;
  162.             end;
  163.          end;
  164.       end; -- propagate
  165.    
  166.    fill_up (col : INTEGER) : BOOLEAN is
  167.       require
  168.          col >= 1;
  169.       local
  170.          stop : BOOLEAN;
  171.          nb : INTEGER;
  172.       do
  173.          if col > size then
  174.             Result := true;
  175.          else
  176.             from  
  177.                stop := false;
  178.                nb := max;
  179.             until
  180.                stop
  181.             loop
  182.                if belongs_to(nb) then
  183.                   nb := nb - 1;
  184.                   stop := (nb = 0);
  185.            elseif propagate(col,nb) then          
  186.                   if  fill_up(col + 1) then            
  187.                      stop := true;
  188.                   else
  189.                      clear_column(col);
  190.                      nb := nb - 1;
  191.                      stop := (nb = 0);
  192.                   end;
  193.                else
  194.                   nb := nb - 1;
  195.                   stop := (nb = 0);
  196.                end;
  197.             end;
  198.             Result := (nb > 0);
  199.          end;
  200.       end; -- fill_up
  201.    
  202. feature {NONE}
  203.    
  204.    elem: ARRAY[INTEGER];
  205.    
  206.    case_vide : INTEGER is 0;
  207.    
  208.    biggest_one: INTEGER is 10;
  209.    
  210.    indice (lig,col : INTEGER): INTEGER is
  211.       require
  212.          lig_trop_petit: lig >= 1 ;
  213.          lig_trop_grand: lig <= size ;
  214.          col_trop_petit: col >= 1 ;
  215.          col_trop_grand: col <= size ;
  216.       local
  217.          l : INTEGER ;
  218.       do
  219.          l:= size - lig + 1;
  220.      Result := max - ((l * (l + 1)) // 2) + col;
  221.       ensure
  222.          Result >= 1 ;
  223.          Result <= max ;
  224.       end; -- indice
  225.    
  226.    clear_column (col : INTEGER) is
  227.       require
  228.          col >= 1;
  229.          col <= size;
  230.       local
  231.          lig : INTEGER;
  232.       do
  233.          from  
  234.             lig := 1;
  235.          until
  236.             lig > col
  237.          loop
  238.             elem.put(case_vide,indice(lig,col-lig+1));
  239.             lig := lig + 1;
  240.          end;
  241.       end; -- clear_column
  242.  
  243. end --  PYRAMID
  244.